package com.zp.self.module.level_4_算法练习.算法.深度优先搜索.回溯;

import java.util.*;

/**
 * @author By ZengPeng
 */
public class 力扣_93_复原IP地址 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_93_复原IP地址().restoreIpAddresses("101023"));
//        System.out.println(new 力扣_93_复原IP地址().restoreIpAddresses("0000"));
//        System.out.println(new 力扣_93_复原IP地址().restoreIpAddresses("25525511135"));
    }

    /**
    题目：有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

     例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
     给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。
     你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

     示例 1：
     输入：s = "25525511135"
     输出：["255.255.11.135","255.255.111.35"]

     示例 2：
     输入：s = "0000"
     输出：["0.0.0.0"]

     示例 3：
     输入：s = "101023"
     输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

    分析：【PR 💖💖💖💖💖】
       1.回溯法：总共有3个分割点，后续碰到0开头只能加分割点了，第一个<2可以接3个值，直接判断3个字符串组成的数字
                变量：起点index，已经标记的分割点位置Deque存储
            --执行用时：2 ms, 在所有 Java 提交中击败了74.69%的用户
     
    边界值 & 注意点：
       1.
     **/
    public List<String> restoreIpAddresses(String s) {
        char[] chars = s.toCharArray();
        List<String> res = new ArrayList<>();
        if(s.length()>12) return res;
        Deque<Integer> queue =new ArrayDeque<>();//在节点后加.
        dfs(chars,0,queue,res);
        return res;
    }
    private void dfs(char[] chars, int index, Deque<Integer> queue, List<String> res) {
        if(chars.length==index) return;
        if(queue.size()==3){
            Integer last = queue.getLast();
            if( chars.length-last>4 || last ==chars.length-1 || (chars[last+1]=='0'&& last!=chars.length-2))  //过滤掉不符合要求的
                return;
            int current =0;//计算最后一个节点后面值的大小
            for (int i = last+1;i<chars.length; i++)
                current= 10*current+(chars[i]-'0');
            if(current>255)
                return;
            StringBuilder sb = new StringBuilder();
            Deque<Integer> queue2 = new ArrayDeque<>(queue);
            int start=0;
            while (!queue2.isEmpty()){//构造字符串
                Integer end = queue2.poll();
                sb.append(chars,start,end-start+1).append('.');
                start=end+1;
            }
            sb.append(chars,start,chars.length-start);
            res.add(sb.toString());
            return;
        }

        if(chars[index]=='0'){//如果开头就是0 ，则直接加点
            queue.add(index);
            dfs(chars,index+1,queue,res);
            queue.pollLast();
        }else {
            int current =0;//计算当前值的大小
            for (int i = index; i < index+3 && i<chars.length; i++) {
                current= 10*current+(chars[i]-'0');
                if(current<256){
                    queue.add(i);
                    dfs(chars,i+1,queue,res);
                    queue.pollLast();
                }
            }
        }
    }
}
